package practise.leetcode.q64;

public class Solution {
    public int minPathSum(int[][] grid) {
        int rows = grid.length;
        int cols = 0;
        if (rows > 0) {
            cols = grid[0].length;
        }

        if (rows == 0 || cols == 0) {
            return 0;
        }

        int[][] dp = new int[rows][cols];
        dp[0][0] = grid[0][0];

        for (int row = 1; row < rows; row++) {
            dp[row][0] = dp[row - 1][0] + grid[row][0];
        }

        for (int col = 1; col < cols; col++) {
            dp[0][col] = dp[0][col - 1] + grid[0][col];
        }

        for (int row = 1; row < rows; row++) {
            for (int col = 1; col < cols; col++) {
                dp[row][col] = Math.min(dp[row - 1][col], dp[row][col -1]) + grid[row][col];
            }
        }

        return dp[rows - 1][cols - 1];
    }
}
